package com.atguigu.distributed.lock.leecode.tree;

import com.atguigu.distributed.lock.leecode.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 层序遍历二叉树
 */
public class LevelOrder {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dns(root,0);
        return list;
    }
    public void dns(TreeNode node,int level){
        if(node==null){
            return;
        }
        //此处很精妙，只有当第一次调用dns方法时，才会增加一个集合，再次调用就不会再新增集合了
        if(list.size()==level){
            list.add(level,new ArrayList<Integer>());
        }
        list.get(level).add(node.data);
        dns(node.left,level+1);
        dns(node.right,level+1);
    }
    List<List<Integer>> list2 = new ArrayList<>();
    public List<List<Integer>> levelOrder2(TreeNode root){
        dns2(root,0);
        return list2;
    }
    public void dns2(TreeNode root,int level){

        if(root==null){
            return;
        }
        if(list2.size()==level){
            list2.add(level,new ArrayList<Integer>());
        }

        list2.get(level).add(root.data);
        if(root.left!=null){
            dns2(root.left,level+1);
        }
        if(root.right!=null){
            dns2(root.right,level+1);
        }
    }



}
